package Lee_code;

import java.util.ArrayList;
import java.util.List;

/**
 * @author blh
 * @date 2024年07月01日 10:34
 */
public class Lee_113_71 {
    List<List<Integer>> res = new ArrayList<>();
    int end;

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        end = targetSum;
        if (root == null) {
            return res;
        }
        ArrayList<Integer> list = new ArrayList<>();
        list.add(root.val);
        backTrace(list, root);
        return res;
    }

    private void backTrace(ArrayList<Integer> list, TreeNode root) {
        int sum = list.stream().mapToInt(Integer::intValue).sum();
        if (sum == end && root.right == null && root.left == null) {
            res.add(new ArrayList<>(list));
        }  else {
            if (root.right != null) {
                list.add(root.right.val);
                backTrace(list, root.right);
                list.remove(list.size() - 1);
            }
            if (root.left != null) {
                list.add(root.left.val);
                backTrace(list, root.left);
                list.remove(list.size() - 1);
            }
        }
    }
}
